1. Field of the Invention
This invention relates to computer networks and, more particularly, to a method for improving the performance of lookup operations for objects distributed among different computer systems in a computer network.
2. Description of the Related Art
Peer-to-peer networking has seen rapid growth in recent years. A peer-to-peer or P2P network is generally used to describe a decentralized network of peer computing nodes, where each node may have similar capabilities and/or responsibilities. A pure peer-to-peer network may not utilize centralized servers. Instead, a given peer node may be equally capable of serving as either a client or a server for other peer nodes. Thus, participating peer nodes in the peer-to-peer network may communicate directly with each other. Work may be done and information may be shared through interaction among the peers.
A peer-to-peer network may be created to fulfill some specific need, or it may be created as a general-purpose network. Some P2P networks are created to deliver one type of service and thus typically run one application. For example, Napster was created to enable users to share music files. Other P2P networks are intended as general purpose networks which may support a large variety of applications. Any of various kinds of distributed applications may execute on a P2P network. Exemplary peer-to-peer applications include file sharing, messaging applications, distributed data storage, distributed processing, etc.
Nodes in a peer-to-peer network often need to access files or other information stored on other nodes in the peer-to-peer network. To access a particular file or particular information, a node may first need to determine which node the file or information is stored on in the peer-to-peer network. Determining which node the file or information is stored on is referred to herein as a lookup operation. Peer-to-peer systems capable of performing lookup operations have been developed, including PASTRY, CHORD, TAPESTRY, and SYMPHONY. In existing peer-to-peer networks, a lookup operation is typically performed by the node needing to access the file sending a query to one or more other nodes to determine the file's location. The query may be propagated on to other nodes in the network until reaching a node that knows where the file is located. Information specifying the file location may then be propagated back from this node to the node that originally issued the query.
This technique of performing a lookup operation takes multiple hops. In a peer-to-peer network having N nodes, the average latency for such a lookup operation is on the order of log(N). In comparison with centralized networking schemes, this is a very high latency operation and limits the performance of the system. Thus, it would be desirable to provide a technique for improving the performance of lookup operations for a peer-to-peer network.